//
//Copyright GX. Yuan
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//   http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

/**
 * @file net.go
 * @brief Leetcode 剑指Offer 第二版
 * @details 剑指 Offer 36. 二叉搜索树与双向链表
 * @author GX. Yuan  any question please send mail to yuanguanxu@qq.com
 * @date 2021-6-28
 * @version V1.0
 * @attention 硬件平台: windows 10 家庭版
 * SDK版本：Go 1.16.5
 * IDE版本：GoLand 2020.2.3
 */
class Node
{
public:
    int val;
    Node *left;
    Node *right;
    Node() {}
    Node(int _val)
    {
        val = _val;
        left = NULL;
        right = NULL;
    }

    Node(int _val, Node *_left, Node *_right)
    {
        val = _val;
        left = _left;
        right = _right;
    }
};

class Solution {
public:
    Node* treeToDoublyList(Node* root) {
        if(root == nullptr) return nullptr; // 为空的话，直接返回
        dfs(root); // 中序遍历
        head->left = pre;
        pre->right = head;
        return head;
    }
private:
    Node *pre, *head;
    void dfs(Node* cur) {
        if(cur == nullptr) return; // 节点为空那么返回
        
        dfs(cur->left); // 中序遍历
        if(pre != nullptr) pre->right = cur; // 前序节点是否为空，如果为空，间当前节点赋值给头结点，表示是第一个节点;
        else head = cur;
        // 当前节点的前序节点执行pre
        cur->left = pre; 
        // 将当前节点赋值给前序节点;
        pre = cur; 
        
        dfs(cur->right); // 前序遍历的格式
    }
};
// 什么是二叉搜索树
//二叉查找树（Binary Search Tree），（又：二叉搜索树，二叉排序树）它或者是一棵空树，或者是具有下列性质的二叉树：
//若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
//它的左、右子树也分别为二叉排序树。二叉搜索树作为一种经典的数据结构，它既有链表的快速插入与删除操作的特点，又有数组快速查找的优势；
//所以应用十分广泛，例如在文件系统和数据库系统一般会采用这种数据结构进行高效率的排序与检索操作

// 思路：
// 使用中序遍历，二叉搜索树的中序遍历为 递增序列 
// 中序遍历的格式：执行对节点的处理顺序；整个树形结构按照这个进行处理即可。
// dfs(){
// 遍历的边界的处理条件
// dfs(pre) 处理当前节点的之前的节点
// 对当前节点进行处理 指定的处理方式
// dfs(after) 处理当前节点后面的节点
// }


//  递归的处理方式，是非树形结构的处理，方式方式是一致的处理方式；
//  都是递归处理
//  递归处理,如果递归的处理有了顺序那么在树形结构中就是,被称之为遍历方式;